package 算法.leetcode.labuladong.数组和链表;

import 算法.leetcode.offer.base.ListNode;

import java.util.PriorityQueue;

/**
 * @author lchenglong
 * @date 2022/6/15
 */
public class 合并K个升序链表 {
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            // 边界条件
            if (lists.length == 0)return null;
            // 定义一个虚拟头结点
            ListNode dummy = new ListNode(-1);
            ListNode cursor = dummy;
            // 定义个最小堆
            PriorityQueue<ListNode> queue = new PriorityQueue<>(
                    lists.length,(a,b)->(a.val-b.val)
            );
            // 将K个链表的头节点放进去
            for (ListNode listNode : lists){
                if (listNode!=null){
                    queue.add(listNode);
                }
            }
            while (!queue.isEmpty()){
                ListNode poll = queue.poll();
                cursor.next = poll;
                if (poll.next!=null){
                    queue.add(poll.next);
                }
                // 游标滑动
                cursor = cursor.next;
            }
            return dummy.next;

        }
    }
}
